(require :graph)
(in-package :graph-model)

(defparameter *edges-petersen*
  '((1 2) (1 5) (1 9) (2 3) (2 7) (3 4) (3 10) (4 5)
    (4 8) (5 6) (6 7) (6 10) (7 8) (8 9) (9 10)))

(defparameter *paths-petersen*
  '((1 2 3 4 5 1 9 10 6 7 8 9) (2 7) (3 10) (4 8) (5 6)))

(defparameter *gg*
  (graph-from-enodes-and-earcs '() *edges-petersen* nil))

(format t "------------------------------------------------------------------------------
 GG
 edges-petersen       (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*edges-petersen* *gg*)

(defparameter *petersen* (graph-from-paths *paths-petersen* nil))

(format t "------------------------------------------------------------------------------
 Petersen
 paths-petersen    (chemins) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*paths-petersen* *petersen*)

(defparameter *opetersen* (graph-from-paths *paths-petersen* t))

(format t "------------------------------------------------------------------------------
 oPetersen
 paths-petersen    (chemins) : ~A
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*paths-petersen* *opetersen*)

(defparameter *edges-envelop*
  '((1 2) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (4 5)))

(defparameter *paths-envelop* '((1 2 3 4 5 2 4 1 5)))

(defparameter *envelop*
  (graph-from-enodes-and-earcs '() *edges-envelop* nil))

(format t "------------------------------------------------------------------------------
 Envelop
 edges-envelop        (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*edges-envelop* *envelop*)

(defparameter *envelop*
  (graph-from-paths *paths-envelop* nil))

(format t "------------------------------------------------------------------------------
 Envelop
 paths-envelop     (chemins) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*paths-envelop* *envelop*)

(defparameter *oenvelop*
  (graph-from-enodes-and-earcs '() *edges-envelop* t))

(format t "------------------------------------------------------------------------------
 oEnvelop
 edges-envelop        (arcs) : ~A
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*edges-envelop* *oenvelop*)

(defparameter *oenvelop*
  (graph-from-paths *paths-envelop* t))

(format t "------------------------------------------------------------------------------
 oEnvelop
 paths-envelop     (chemins) : ~A
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*paths-envelop* *oenvelop*)

(defparameter *arcs-go* '((1 2) (1 4) (2 4)  (3 2) (4 3)))
(defparameter *go* (graph-from-enodes-and-earcs '((5)) *arcs-go* t))

(format t "------------------------------------------------------------------------------
 GO
 nodes              (noeuds) : ((5))
 arcs-go              (arcs) : ~A
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*arcs-go* *go*)

(defparameter *arcs-bp* '((1 4) (1 5) (2 6) (3 6) (5 2)))
(defparameter *bp* (graph-from-enodes-and-earcs '() *arcs-bp* t))

(format t "------------------------------------------------------------------------------
 BP
 arcs-bp              (arcs) : ~A
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*arcs-bp* *bp*)

(defparameter *arcs-508* '((0 5 5) (0 3 3) (3 5 2) (3 9 6) (5 3 1) (5 9 4) (5 11 6) (9 11 2) (11 0 3) (11 9 7)))

(defparameter *o508* (graph-from-enodes-and-earcs '() *arcs-508* t))
(defparameter *508* (graph-from-enodes-and-earcs '() *arcs-508* nil))

(format t "------------------------------------------------------------------------------
 o508
 arcs-508             (arcs) : ~A
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*arcs-508* *o508*)

(format t "------------------------------------------------------------------------------
 508
 arcs-508             (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*arcs-508* *508*)

(defparameter *edges-490* '((1 2 4) (2 3 8) (3 4 7) (4 5 9) (5 6 10) (6 7 2)
			    (7 8 1) (8 1 8)
			    (2 8 11) (8 9 7) (3 9 2) (3 6 4) (9 6 14)))

(defparameter *490* (graph-from-enodes-and-earcs '() *edges-490* nil))

(format t "------------------------------------------------------------------------------
 490
 edges-490            (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*edges-490* *490*)

(defparameter *vertex* (graph-from-enodes-and-earcs '((1)) '() nil))
(defparameter *overtex* (graph-from-enodes-and-earcs '((1)) '() t))

(format t "------------------------------------------------------------------------------
 Vertex
 nodes              (noeuds) : ((1))
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*vertex*)

(format t "------------------------------------------------------------------------------
 oVertex
 nodes              (noeuds) : ((1))
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*overtex*)

(defparameter *edges-434* '((1 2) (1 3) (2 3) (2 4) (5 6) (5 7) (8 9)))
(defparameter *434* (graph-from-enodes-and-earcs '((10)) *edges-434* nil))

(format t "------------------------------------------------------------------------------
 434
 nodes              (noeuds) : ((10))
 edges-434            (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*edges-434* *434*)

(defparameter *arcs-518* '((1 2 10) (1 4 5) (2 3 1) (2 4 2) (3 5 4) (4 2 3) (4 3 9) (4 5 2) (5 1 7) (5 3 6)))
(defparameter *518* (graph-from-enodes-and-earcs '() *arcs-518* t))

(format t "------------------------------------------------------------------------------
 518
 arcs-518             (arcs) : ~A
 graphe orienté              : ~A
------------------------------------------------------------------------------~%~%"
	*arcs-518* *518*)

(defparameter *edges-wiki-dijkstra* '((1 2 7) (1 3 9) (1 6 14)
				  (2 3 10) (2 4 14)
				  (3 4 11) (3 6 2)
				  (4 5 6) (5 6 9)))
(defparameter *wiki-dijkstra* (graph-from-enodes-and-earcs '() *edges-wiki-dijkstra* nil))

(format t "------------------------------------------------------------------------------
 Wiki-dijkstra
 edges-wiki-dijkstra  (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*edges-wiki-dijkstra* *wiki-dijkstra*)

(defparameter *edges-wiki-prim* '((1 2 7) (1 4 5) (2 3 8) (2 4 9) (2 5 7)
			       (3 5 5) (4 5 15) (4 6 6) (5 6 9) (5 7 9)
			       (6 7 11)))

(defparameter *wiki-prim* (graph-from-enodes-and-earcs '() *edges-wiki-prim* nil))

(format t "------------------------------------------------------------------------------
 Wiki-prim
 edges-wiki-prim      (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*edges-wiki-prim* *wiki-prim*)

(defparameter *igrid*
  (graph-from-enodes-and-earcs
   '()
   '((0 1) (0 2) (0 3) (0 4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4)
     (1 5) (2 5) (2 6) (3 5) (3 6) (3 7) (4 5) (4 6) (4 7) (4 8)
     (5 6) (5 7) (5 8) (5 9) (6 7) (6 8) (6 9) (7 8) (7 9) (8 9)
     (6 10) (7 10) (7 11) (8 10) (8 11) (8 12) (9 10) (9 11) (9 12) (9 13)
     (10 11) (10 12) (10 13) (10 14) (11 12) (11 13) (11 14) (12 13) (12 14) (13 14)
     (11 15) (12 15) (12 16) (13 15) (13 16) (13 17) (14 15) (14 16) (14 17) (14 18)
     (15 16) (15 17) (15 18) (15 19) (16 17) (16 18) (16 19) (17 18) (17 19) (18 19))
   nil))

(format t "------------------------------------------------------------------------------
 Igrid
 arcs                 (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	'((0 1) (0 2) (0 3) (0 4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4)
	  (1 5) (2 5) (2 6) (3 5) (3 6) (3 7) (4 5) (4 6) (4 7) (4 8)
	  (5 6) (5 7) (5 8) (5 9) (6 7) (6 8) (6 9) (7 8) (7 9) (8 9)
	  (6 10) (7 10) (7 11) (8 10) (8 11) (8 12) (9 10) (9 11) (9 12) (9 13)
	  (10 11) (10 12) (10 13) (10 14) (11 12) (11 13) (11 14) (12 13) (12 14) (13 14)
	  (11 15) (12 15) (12 16) (13 15) (13 16) (13 17) (14 15) (14 16) (14 17) (14 18)
	  (15 16) (15 17) (15 18) (15 19) (16 17) (16 18) (16 19) (17 18) (17 19) (18 19))
	*igrid*)

(defparameter *villes-arcs*
  '(((1 "Paris") (2 "Lyon") 2)
    ((2 "Lyon") (3 "Marseille") 2)
    ((4 "Toulouse") (5 "Bordeaux") 2)
    ((1 "Paris") (5 "Bordeaux") 3)
    ((3 "Marseille") (4 "Toulouse") 5)))
  
(defparameter *villes*
  (graph-from-enodes-and-earcs '((0 "Ajaccio")) *villes-arcs* nil))

(format t "------------------------------------------------------------------------------
 Villes
 villes-arcs          (arcs) : ~A
 graphe non-orienté          : ~A
------------------------------------------------------------------------------~%~%"
	*villes-arcs* *villes*)


(format t "~%~%~%~%~%~%~%~%~%~%~%~%
Vous pouvez voir ci-dessus que les différents graphes du
fichier \"data-graphs.lisp\" se sont créés.

Si vous désirez poursuivre les tests, vous devez vous
placer dans le package \"graph-model\" grâce à la commande
\(in-package :graph-model).



Pour continuer le test en visonnant les pdf, pratique plus
conviviale, tapez
\(show-test-pdf)

Pour continuer au format standard, tapez
\(show-test-standard)")	
  
(defparameter *villes-minimum-spanning-tree*
  (minimum-spanning-tree *villes*))
(defparameter *not-oriented-opetersen*
  (make-graph-not-oriented *opetersen*))
(defparameter *reverse-oenvelop*
  (reverse-graph-arcs *oenvelop*))
(defparameter *ovilles*
  (graph-from-enodes-and-earcs '((0 "Ajaccio")) *villes-arcs* t))
(defparameter *weight-arcs-go* '((1 2 5) (1 4 3) (2 4 2)  (3 2 4) (4 3 8)))
(defparameter *weight-go* (graph-from-enodes-and-earcs '((5)) *weight-arcs-go* t))


(defparameter *numero-de-tuto* 0)

(defun etape-to-zero()
  (setf *numero-de-tuto* 0))

(defun etape-i ()
  *numero-de-tuto*)

(defun show-test-pdf ()
  (format t "Le 'tutoriel' de test va commencer.~%~%
Le 'tutoriel' se déroule étape par étape
tapez (etape) pour atteindre la premiere étape.
~%~%~%~%~%"))
 
(defun etape ()
  (incf *numero-de-tuto*)
  (cond
    ((= 1 (etape-i))
     (progn
       (format t "Commençons par transposer un graphe orienté
en un graphe non orienté. Voyons le graphe orienté.~%")
       (graph-to-dot-format *opetersen*)
       
       (format t "Maintenant, voyons le graphe non-orienté.~%")
       (graph-to-dot-format *not-oriented-opetersen*)
       
       (format t "Tapez (etape) pour poursuivre.~%")))
    
    ((= 2 (etape-i))
     (progn
       (format t "Voyons la fonction qui inverse le sens des
arcs d'un graphe orienté. Voici le graphe d'origine.~%")
       (graph-to-dot-format *oenvelop*)

       (format t "Voyons le graphe dont les arcs ont été inversés.~%")
       (graph-to-dot-format *reverse-oenvelop*)
       
       (format t "Tapez (etape) pour poursuivre.~%")))

    ((= 3 (etape-i))
     (progn
       (format t "Passons à une fonction moins bavarde,
existe-t-il un chemin entre les noeuds 'Bordeaux' et
'Lyon' ?~%")
       (graph-to-dot-format *ovilles*)
       
       (format t "La réponse est ~A. Cependant, un chemin
entre 'Lyon' et 'Bordeaux' existe-t-il ? et bien... ~A~%"
	       (if (pathway-from-n1-to-n2-p
		    (find-node 5 *ovilles*)
		    (find-node 2 *ovilles*)
		    *ovilles*)
		   "Oui"
		   "Non")
	       (if (pathway-from-n1-to-n2-p
		    (find-node 2 *ovilles*)
		    (find-node 5 *ovilles*)
		    *ovilles*)
		   "Oui"
		   "Non"))
       (format t "Tapez (etape) pour poursuivre.~%")))

    ((= 4 (etape-i))
     (progn
       (format t "Reprenons le même graphe et voyons la liste
des noeuds accessibles depuis 'Lyon', si vous voulez afficher
le graphe une nouvelle fois tapez :
\(graph-to-dot-format *ovilles*)

Les noeuds accessibles depuis 'Lyon' sont les suivants : 
~A~%" (accessible-nodes-from (find-node 2 *ovilles*) *ovilles*))
       (format t "Tapez (etape) pour poursuivre.~%")))

    ((= 5 (etape-i))
     (progn
       (format t "Changeons de graphe.")
       (graph-to-dot-format *bp*)
       
       (format t "
Les noeuds connectés au noeud 1 : 
~A~%~%~%~%" (connected-nodes (find-node 1 *bp*) *bp*))
       (format t "Et oui, les noeuds connectés au noeud 1
ce sont tous les noeuds du graphe, en effet, ce graphe est
connexe.

Si vous ne me croyez pas, vous pouvez tester, utilisez :
\(connex-p *bp*)~%")
       (format t "Tapez (etape) pour poursuivre.~%")))

    ((= 6 (etape-i))
     (progn
       (format t "Dans un nouveau graphe, suivant, affichons
tous les chemins entre les noeuds 1 et 4.~%")
       (graph-to-dot-format *weight-go*)

       (format t "Voici la liste des chemins de 1 à 4 :
~A~%~%" (pathways-from-n1-to-n2 (find-node 1 *weight-go*)
			      (find-node 4 *weight-go*)
			      *weight-go*))

       (format t "Et maintenant, le plus court chemin entre
1 et 4 : ~A~%" 
	       (shortest-pathway-from-n1-to-n2
		(find-node 1 *weight-go*)
		(find-node 4 *weight-go*)
		*weight-go*))
       (format t "Tapez (etape) pour poursuivre.~%")))

    ((= 7 (etape-i))
     (progn
       (format t "Prenons maintenant le graphe \"Villes\"
du fichier \"data-graph.lisp\".")
       (graph-to-dot-format *villes*)
       
       (format t "Qui ce transforme en ce graphe lorsqu'on extrait
l'arbre couvrant de poids minimum~%")
       (graph-to-dot-format *villes-minimum-spanning-tree*)
       (format t "Tapez (etape) pour poursuivre.~%")))


    ((= 8 (etape-i))
     (progn
       (format t "Merci d'avoir suivi le 'Tutoriel' jusqu'au
bout.~%")
       (etape-to-zero)))))





(defun show-test-standard ()
  (format t "Commençons par transposer un graphe orienté
en un graphe non orienté. Voyons le graphe orienté.
------------------------------------------------------------------------------
 oPetersen
 graphe orienté             : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	*opetersen* (graph-arcs *opetersen*))
       
  (format t "Maintenant, voyons le graphe non-orienté.
------------------------------------------------------------------------------
 Not-oriented-oPetersen
 graphe non-orienté         : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *not-oriented-opetersen*
	  (graph-arcs *not-oriented-opetersen*))
  
(format t "




")  

  (format t "Voyons la fonction qui inverse le sens des
arcs d'un graphe orienté. Voici le graphe d'origine.
------------------------------------------------------------------------------
 oEnvelop
 graphe orienté             : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *oenvelop*
	  (graph-arcs *oenvelop*))
  
  (format t "Voyons le graphe dont les arcs ont été inversés.
------------------------------------------------------------------------------
 Reverse-oEnvelop
 graphe orienté             : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *reverse-oenvelop*
	  (graph-arcs *reverse-oenvelop*))
       
(format t "




")  

  (format t "Passons à une fonction moins bavarde,
existe-t-il un chemin entre les noeuds 'Bordeaux' et
'Lyon' ?
------------------------------------------------------------------------------
 oVilles
 graphe orienté             : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *ovilles*
	  (graph-arcs *ovilles*))
  
  (format t "La réponse est ~A. Cependant, un chemin
entre 'Lyon' et 'Bordeaux' existe-t-il ? et bien... ~A~%"
	  (if (pathway-from-n1-to-n2-p
	       (find-node 5 *ovilles*)
	       (find-node 2 *ovilles*)
	       *ovilles*)
	      "Oui"
	      "Non")
	  (if (pathway-from-n1-to-n2-p
	       (find-node 2 *ovilles*)
	       (find-node 5 *ovilles*)
	       *ovilles*)
	      "Oui"
	      "Non"))
(format t "




")  


  (format t "Reprenons le même graphe et voyons la liste
des noeuds accessibles depuis 'Lyon'.
------------------------------------------------------------------------------
 oVilles
 graphe orienté             : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%


Les noeuds accessibles depuis 'Lyon' sont les suivants : 
~A~%"
	  *ovilles*
	  (graph-arcs *ovilles*)
	  (accessible-nodes-from (find-node 2 *ovilles*) *ovilles*))


(format t "




") 

  (format t "Changeons de graphe.
------------------------------------------------------------------------------
 BP
 graphe orienté             : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *bp*
	  (graph-arcs *bp*))

  (format t "
Les noeuds connectés au noeud 1 : 
~A~%~%~%~%" (connected-nodes (find-node 1 *bp*) *bp*))
  (format t "Et oui, les noeuds connectés au noeud 1
ce sont tous les noeuds du graphe, en effet, ce graphe est
connexe.

Si vous ne me croyez pas, vous pouvez tester, utilisez :
\(connex-p *bp*)")


(format t "




")  

  (format t "Dans un nouveau graphe, suivant, affichons
tous les chemins entre les noeuds 1 et 4.
------------------------------------------------------------------------------
 Weight-Go
 graphe orienté             : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *weight-go*
	  (graph-arcs *weight-go*))

  (format t "Voici la liste des chemins de 1 à 4 :
~A~%~%~%~%"
	  (pathways-from-n1-to-n2 (find-node 1 *weight-go*)
				  (find-node 4 *weight-go*)
				  *weight-go*))
  
  (format t "Et maintenant, le plus court chemin entre
1 et 4 : ~A~%" 
	  (shortest-pathway-from-n1-to-n2
	   (find-node 1 *weight-go*)
	   (find-node 4 *weight-go*)
	   *weight-go*))

(format t "




")  


  (format t "Prenons maintenant le graphe \"Villes\"
du fichier \"data-graph.lisp\".
------------------------------------------------------------------------------
 Villes
 graphe non-orienté         : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *villes*
	  (graph-arcs *villes*))
  
  (format t "Qui ce transforme en ce graphe lorsqu'on extrait
l'arbre couvrant de poids minimum~%")
  (format t "------------------------------------------------------------------------------
 Villes-minimum-spanning-tree
 graphe non-orienté         : ~A
 arcs du graphe             : ~A
------------------------------------------------------------------------------~%~%"
	  *villes-minimum-spanning-tree*
	  (graph-arcs *villes-minimum-spanning-tree*))

)
